#lang racket
(require (planet dherman/memoize:3:1))

(provide identity
         list-fibs-up-to
         next-prime
         nth-prime
         prime?
         prime-factors
         square
         sum)

(define (identity x) x)

(define (square x) (* x x))

(define (sum term a next b)
  (if (> a b) 0 (+ (term a) (sum term (next a) next b))))
      
(define/memo (fib n) 
  (if (<= n 1) 1 (+ (fib (- n 1)) (fib (- n 2)))))

(define (list-fibs-up-to n) 
  (list-fibs n 0))

(define (list-fibs max index)
  (if (> (fib index) max) 
      '()
      (cons (fib index) (list-fibs max (add1 index)))))

(define (prime-factors n)
  (if (> n 1)
    (do ((x 2 (add1 x)))
      ((zero? (remainder n x))
       (cons x (prime-factors (/ n x)))))
    '()))

(define (prime? n) 
  (cond ((equal? n 2) #t)
        ((even? n) #f)
        (else (prime-helper n 3))))

(define/memo (prime-helper n d)
  (cond ((> (square d) n) #t)
        ((= (remainder n d) 0) #f)
        (else (prime-helper n (+ d 2)))))

(define (next-prime n)
  (if (odd? n)
      (next-prime-helper (+ 2 n))
      (next-prime-helper (+ 1 n))))

(define/memo (next-prime-helper n)
  (cond ((prime? n) n)
        ((next-prime-helper (+ 2 n)))))

(define (nth-prime n)
  (if (= n 0) 
      2
      (nth-prime-helper 2 0 n)))

(define/memo (nth-prime-helper last-prime current-index target-index)
  (cond ((>= current-index target-index) last-prime)
        (else (nth-prime-helper (next-prime last-prime) (+ 1 current-index) target-index))))